#include <iostream>
#include <string.h>
#include <string>
using namespace std;

template <class T>
class list; // 必须提前声明list模板类，以便在node类中使用，不然报错

template <class T>
class node // 单链表节点类
{
private:
    T data;               // 数据域
    node<T> *next;        // 指针域
    friend class list<T>; // 友元
};

template <class T>
class list // 单链表类
{
private:
    int length;     // 链表长度
    node<T> *pHead; // 头指针
    node<T> *pRear; // 尾指针
public:
    list()
    {
        length = 0;
        pHead = pRear = NULL; // 初始化，无头单链表
    }
    void push_back(T t) // 尾插
    {
        node<T> *p = new node<T>;
        p->data = t;
        p->next = NULL;
        if (pRear == NULL) // 插入第一个数据
        {
            pHead = pRear = p;
        }
        else
        {
            pRear->next = p;
            pRear = p; // 更新尾节点
        }
        length++;
    }

    void push_front(T t) // 头插
    {
        node<T> *p = new node<T>;
        p->data = t;
        if (pHead == NULL) // 第一次头插
        {
            pRear = p;
        }
        p->next = pHead;
        pHead = p; // 更新头节点
        length++;
    }

    void insert(T t, int pos) // 在指定位置插入
    {
        if (pos > length)
        {
            cout << "invalid index" << endl;
            return;
        }
        node<T> *p = pHead;
        if (pos == 1) // 插入到第一个位置
        {
            push_front(t);
            return;
        }
        for (int i = 0; i < pos - 2; i++)
            p = p->next; // 移动到前面一个位置
        node<T> *q = new node<T>;
        q->data = t;
        q->next = p->next;
        p->next = q;
        length++;
    }

    void updata(T t, int pos) // 修改数据
    {
        if (pos > length)
        {
            cout << "invalid index" << endl;
            return;
        }
        node<T> *p = pHead;
        for (int i = 0; i < pos - 1; i++)
            p = p->next; // 移动到前面一个位置
        cout << "单链表的第" << pos << "个元素是:" << p->data << endl;
        p->data = t;
    }

    void del(int pos) // 删除数据
    {
        if (pos > length)
        {
            cout << "invalid index" << endl;
            return;
        }
        node<T> *p = pHead;
        if (pos == 1) // 删除第一个元素
        {
            node<T> *temp = p->next;
            delete p;
            pHead = temp;
            length--;
            return;
        }
        for (int i = 0; i < pos - 2; i++)
            p = p->next; // 移动到前面一个位置
        node<T> *q = p->next;
        p->next = q->next;
        delete q;
        if (pos == length) // 删除最后面一个元素
        {
            pRear = p;
        }
        length--;
    }

    void showList() // 遍历打印链表
    {
        node<T> *p = pHead;
        for (int i = 0; i < length; i++)
        {
            if (i == length - 1)
            {
                cout << p->data << endl;
                break;
            }
            cout << p->data << "->";
            p = p->next;
        }
    }
    
    ~list()
    {
        node<T> *p, *q;
        p = pHead;
        for (int i = 0; i < length; i++)
        {
            q = p->next;
            delete p;
            p = q;
        }
    }
};

int main()
{
    list<float> l1;
    for (int i = 1; i <= 6; i++)
        l1.push_front(i * 11.1); // 前插
    l1.showList();

    l1.updata(25.1, 2); // 修改
    l1.showList();

    l1.push_back(666); // 尾插
    l1.push_back(777);
    l1.showList();

    l1.insert(315, 1);
    l1.showList();

    l1.del(9); //
    l1.push_back(512);
    l1.showList();
    l1.del(1); //
    l1.push_front(666);
    l1.showList();

    return 0;
}